package top;


import java.util.List;

/**
 *
 * 奇偶链表
 *
 * @author chenyw
 * @date 2022/7/21 11:17
 */
public class Top328oddEvenList {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //p为奇链表的尾节点
        ListNode p = head;
        //q为偶链表的尾节点
        ListNode q = head.next;
        ListNode o = q;
        //必须先判奇再判偶
        while (p.next != null && q.next != null) {
            p.next = q.next;
            p = p.next;
            q.next = p.next;
            q = q.next;
        }
        //合并
        p.next = o;
        return head;
    }
}
